package leetcodecompetition.S119;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2023-12-09-23:52
 * @Description: 1.0
 */
public class T100140 {
    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        int[][] mp = creatTable(roads, n);
        int res = 0;
        for (int mark = 0; mark < 1 << n; mark++) {
            int[][] r = floyd(copy(mp, n), mark);
            if (check(r, n, mark, maxDistance)) res++;
        }
        return res;
    }

    public boolean check(int[][] mp, int n, int mark, int maxDistance) {
        for (int i = 0; i < n; i++) {
            if (((mark >> i) & 1) == 1) continue;
            for (int j = 0; j < n; j++) {
                if (((mark >> j) & 1) == 1) continue;
                if (mp[i][j] > maxDistance) return false;
            }
        }
        return true;
    }

    public int[][] copy(int[][] mp, int n) {
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(mp[i], 0, f[i], 0, n);
        }
        return f;
    }

    public int[][] creatTable(int[][] edges, int n) {
        int[][] mp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(mp[i], Integer.MAX_VALUE / 2);
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1], weight = e[2];
            mp[from][to] = Math.min(mp[from][to], weight);
            mp[to][from] = Math.min(mp[to][from], weight);
        }
        return mp;
    }

    public int[][] floyd(int[][] mp, int mark) {
        int n = mp.length;
        for (int k = 0; k < n; ++k) {
            if (((mark >> k) & 1) == 1) continue;
            mp[k][k] = 0;
            for (int i = 0; i < n; ++i) {
                if (((mark >> i) & 1) == 1) continue;
                for (int j = 0; j < n; ++j) {
                    mp[i][j] = Math.min(mp[i][j], mp[i][k] + mp[k][j]);
                }
            }
        }
        return mp;
    }

    @Test
    public void test() {
        System.out.println(numberOfSets(3, 5, new int[][]{{0, 1, 20}, {0, 1, 10}, {1, 2, 2}, {0, 2, 2}}));
    }
}
